home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgLangD.iso / BORLAND TURBO / CLASSINC.PAK / DLISTIMP.H < prev    next >
C/C++ Source or Header  |  1997-05-05  |  35KB  |  1,179 lines
  1. //----------------------------------------------------------------------------
  2. // Borland BIDS Container Library
  3. // Copyright (c) 1991, 1997 by Borland International, All Rights Reserved
  4. //
  5. //$Revision:   5.8  $
  6. //
  7. //----------------------------------------------------------------------------
  8. #if !defined( CLASSLIB_DLISTIMP_H )
  9. #define CLASSLIB_DLISTIMP_H
  10.  
  11. #if !defined( __LIMITS_H )
  12. #include <limits.h>
  13. #endif
  14.  
  15. #if !defined( SERVICES_CHECKS_H )
  16. #include <services/checks.h>
  17. #endif
  18.  
  19. #if !defined( CLASSLIB_DEFS_H )
  20. #include <classlib/defs.h>
  21. #endif
  22.  
  23. #if !defined( CLASSLIB_MEMMGR_H )
  24. #include <classlib/memmgr.h>
  25. #endif
  26.  
  27. #if !defined( CLASSLIB_ALLOCTR_H )
  28. #include <classlib/alloctr.h>
  29. #endif
  30.  
  31. #if !defined( CLASSLIB_VOIDP_H )
  32. #include <classlib/voidp.h>
  33. #endif
  34.  
  35. #pragma option -Vo-
  36. #if defined( BI_CLASSLIB_NO_po )
  37. #pragma option -po-
  38. #endif
  39.  
  40. #if defined(BI_NAMESPACE)
  41. namespace ClassLib {
  42. #endif
  43.  
  44. /*------------------------------------------------------------------------*/
  45. /*                                                                        */
  46. /*  template <class T,class Alloc> class TMDoubleListElement              */
  47. /*                                                                        */
  48. /*  Node for templates TMDoubleListImp<T,Alloc> and                       */
  49. /*  TMIDoubleListImp<T,Alloc>                                             */
  50. /*                                                                        */
  51. /*------------------------------------------------------------------------*/
  52.  
  53. template <class T,class Alloc> class TMDoubleListImp;
  54.  
  55. template <class T,class Alloc> class TMDoubleListBlockInitializer :
  56.     public Alloc
  57. {
  58.  
  59. protected:
  60.  
  61.     TMDoubleListBlockInitializer();
  62.     ~TMDoubleListBlockInitializer();
  63.  
  64.     static unsigned Count;
  65.  
  66. };
  67.  
  68. #if defined( BI_OLDNAMES )
  69. #define BI_DoubleListBlockInitializer TDoubleListBlockInitializer
  70. #endif
  71.  
  72. template <class T,class Alloc>
  73. TMDoubleListBlockInitializer<T,Alloc>::TMDoubleListBlockInitializer()
  74. {
  75.     PRECONDITION( Count != UINT_MAX );
  76.     if( Count++ == 0 )
  77.         TMDoubleListElement<T,Alloc>::Mgr =
  78.             new(*this)TMMemBlocks<Alloc>( sizeof(TMDoubleListElement<T,Alloc>), 20 );
  79. }
  80.  
  81. template <class T,class Alloc>
  82. TMDoubleListBlockInitializer<T,Alloc>::~TMDoubleListBlockInitializer()
  83. {
  84.     PRECONDITION( Count != 0 );
  85.     if( --Count == 0 )
  86.         {
  87.         delete TMDoubleListElement<T,Alloc>::Mgr;
  88.         TMDoubleListElement<T,Alloc>::Mgr = 0;
  89.         }
  90. }
  91.  
  92. template <class T,class Alloc>
  93. unsigned TMDoubleListBlockInitializer<T,Alloc>::Count = 0;
  94.  
  95. template <class T,class Alloc> class TMDoubleListElement
  96. {
  97.  
  98. public:
  99.  
  100.     TMDoubleListElement( const T& t, TMDoubleListElement<T,Alloc> *p ) :
  101.         Data(t)
  102.         {
  103.         Next = p->Next;
  104.         Prev = p;
  105.         p->Next = this;
  106.         Next->Prev = this;
  107.         }
  108.  
  109.     TMDoubleListElement();
  110.  
  111.     TMDoubleListElement<T,Alloc> *Next;
  112.     TMDoubleListElement<T,Alloc> *Prev;
  113.     T Data;
  114.  
  115.     void *operator new( size_t sz );
  116.     void operator delete( void * );
  117.  
  118. private:
  119.  
  120.     friend TMDoubleListBlockInitializer<T,Alloc>;
  121.  
  122.     static TMMemBlocks<Alloc> *Mgr;
  123.  
  124. };
  125.  
  126. #if defined( BI_OLDNAMES )
  127. #define BI_MDoubleListElement TMDoubleListElement
  128. #endif
  129.  
  130. template <class T,class Alloc>
  131. TMMemBlocks<Alloc> *TMDoubleListElement<T,Alloc>::Mgr = 0;
  132.  
  133. template <class T,class Alloc>
  134. inline TMDoubleListElement<T,Alloc>::TMDoubleListElement()
  135. {
  136.     Next = Prev = 0;
  137. }
  138.  
  139. template <class T,class Alloc>
  140. void *TMDoubleListElement<T,Alloc>::operator new( size_t sz )
  141. {
  142.     PRECONDITION( Mgr != 0 );
  143.     return Mgr->Allocate( sz );
  144. }
  145.  
  146. template <class T,class Alloc>
  147. void TMDoubleListElement<T,Alloc>::operator delete( void *b )
  148. {
  149.     PRECONDITION( Mgr != 0 );
  150.     Mgr->Free( b );
  151. }
  152.  
  153. /*------------------------------------------------------------------------*/
  154. /*                                                                        */
  155. /*  template <class T,class Alloc> class TMDoubleListImp                  */
  156. /*                                                                        */
  157. /*  Implements a managed double-linked list of objects of type T.         */
  158. /*  Assumes that T has meaningful copy semantics and a default            */
  159. /*  constructor.                                                          */
  160. /*                                                                        */
  161. /*------------------------------------------------------------------------*/
  162.  
  163. template <class T,class Alloc> class TMDoubleListIteratorImp;
  164.  
  165. template <class T,class Alloc> class TMDoubleListImp :
  166.     private TMDoubleListBlockInitializer<T,Alloc>
  167. {
  168.  
  169.     typedef TMDoubleListBlockInitializer<T,Alloc> Parent;
  170.  
  171. public:
  172.  
  173.     typedef void (*IterFunc)(T&, void *);
  174.     typedef int  (*CondFunc)(const T&, void *);
  175.  
  176.     friend TMDoubleListIteratorImp<T,Alloc>;
  177.  
  178.     TMDoubleListImp()
  179.         {
  180.         InitList();
  181.         }
  182.  
  183.     ~TMDoubleListImp()
  184.         {
  185.         Flush();
  186.         }
  187.  
  188.     const T& PeekHead() const
  189.         {
  190.         return Head.Next->Data;
  191.         }
  192.  
  193.     const T& PeekTail() const
  194.         {
  195.         return Tail.Prev->Data;
  196.         }
  197.  
  198.     int Add( const T& t )
  199.         {
  200.         return AddElement(t,&Head);
  201.         }
  202.  
  203.     int AddAtHead( const T& t )
  204.         {
  205.         return AddElement(t,&Head);
  206.         }
  207.  
  208.     int AddAtTail( const T& t )
  209.         {
  210.         return AddElement(t,Tail.Prev);
  211.         }
  212.  
  213.     int Detach( const T& t )
  214.         {
  215.         return DoDetach(t,0);
  216.         }
  217.  
  218.     int DetachAtHead()
  219.         {
  220.         return DoDetachAtHead(0);
  221.         }
  222.  
  223.     int DetachAtTail()
  224.         {
  225.         return DoDetachAtTail(0);
  226.         }
  227.  
  228.     T *Find( const T& t );
  229.  
  230.     void Flush()
  231.         {
  232.         DoFlush(0);
  233.         }
  234.  
  235.     int IsEmpty() const
  236.         {
  237.         return ItemsInContainer == 0;
  238.         }
  239.  
  240.     int GetItemsInContainer() const
  241.         {
  242.         return ItemsInContainer;
  243.         }
  244.  
  245.     void ForEach( IterFunc iter, void *args );
  246.     T *FirstThat( CondFunc cond, void *args ) const;
  247.     T *LastThat( CondFunc cond, void *args ) const;
  248.  
  249.     Parent::operator delete;
  250. #if !defined(BI_NO_ARRAYNEW)
  251.     Parent::operator delete [];
  252. #endif
  253.  
  254. #if defined( BI_OLDNAMES )
  255.     const T& peekHead() const { return PeekHead(); }
  256.     const T& peekTail() const { return PeekTail(); }
  257.     void add( const T& t ) { Add(t); }
  258.     void addAtTail( const T& t ) { AddAtTail(t); }
  259.     void detach( const T& t, int del = 0 ) { Detach(t); }
  260.     void flush( int = 0 ) { Flush(); }
  261.     int isEmpty() const { return IsEmpty(); }
  262.     int getItemsInContainer() const { return GetItemsInContainer(); }
  263.     void forEach( IterFunc iter, void *args )
  264.         { ForEach( iter, args ); }
  265.     T *firstThat( CondFunc cond, void *args ) const
  266.         { return FirstThat( cond, args ); }
  267.     T *lastThat( CondFunc cond, void *args ) const
  268.         { return LastThat( cond, args ); }
  269. #endif  // BI_OLDNAMES
  270.  
  271. protected:
  272.  
  273.     int DoDetach( const T& t, int del = 0 )
  274.         {
  275.         return DetachElement(FindDetach(t),del);
  276.         }
  277.  
  278.     int DoDetachAtHead( int del = 0 )
  279.         {
  280.         return DetachElement(&Head,del);
  281.         }
  282.  
  283.     int DoDetachAtTail( int del = 0 )
  284.         {
  285.         return DetachElement(Tail.Prev->Prev,del);
  286.         }
  287.  
  288.     void DoFlush( int del = 0 );
  289.  
  290.     TMDoubleListElement<T,Alloc> Head, Tail;
  291.  
  292.     virtual TMDoubleListElement<T,Alloc> *FindDetach( const T& t )
  293.         {
  294.         return FindPred(t);
  295.         }
  296.  
  297.     virtual TMDoubleListElement<T,Alloc> *FindPred( const T& );
  298.  
  299.     int ItemsInContainer;
  300.  
  301. private:
  302.  
  303.     virtual void RemoveData( TMDoubleListElement<T,Alloc> * )
  304.         {
  305.         }
  306.  
  307.     void InitList();
  308.  
  309.     int DetachElement( TMDoubleListElement<T,Alloc> *element, int del = 0 );
  310.     int AddElement( const T& t, TMDoubleListElement<T,Alloc> *element );
  311.  
  312. };
  313.  
  314. template <class T,class Alloc> void TMDoubleListImp<T,Alloc>::InitList()
  315. {
  316.     Head.Next = &Tail;
  317.     Head.Prev = &Head;
  318.     Tail.Prev = &Head;
  319.     Tail.Next = &Tail;
  320.     ItemsInContainer = 0;
  321. }
  322.  
  323. template <class T,class Alloc>
  324. int TMDoubleListImp<T,Alloc>::AddElement( const T& toAdd,
  325.                               TMDoubleListElement<T,Alloc> *Pos )
  326. {
  327.     new TMDoubleListElement<T,Alloc>( toAdd, Pos );
  328.     ItemsInContainer++;
  329.     return 1;
  330. }
  331.  
  332. template <class T,class Alloc>
  333. TMDoubleListElement<T,Alloc> *TMDoubleListImp<T,Alloc>::FindPred( const T&t )
  334. {
  335.     Tail.Data = t;
  336.     TMDoubleListElement<T,Alloc> *cursor = &Head;
  337.     while( !(t == cursor->Next->Data) )
  338.         cursor = cursor->Next;
  339.     Tail.Data = T();
  340.     return cursor;
  341. }
  342.  
  343. template <class T,class Alloc>
  344. int TMDoubleListImp<T,Alloc>::DetachElement(
  345.         TMDoubleListElement<T,Alloc> *pred, int del )
  346. {
  347.     TMDoubleListElement<T,Alloc> *item = pred->Next;
  348.     if( item == &Tail )
  349.         return 0;
  350.     else
  351.         {
  352.         pred->Next = pred->Next->Next;
  353.         pred->Next->Prev = pred;
  354.         if( del != 0 )
  355.             RemoveData( item );
  356.         delete item;
  357.         ItemsInContainer--;
  358.         return 1;
  359.         }
  360. }
  361.  
  362. template <class T,class Alloc>
  363. T *TMDoubleListImp<T,Alloc>::Find( const T& t )
  364. {
  365.     TMDoubleListElement<T,Alloc> *pred = FindPred(t);
  366.     if( pred->Next == &Tail )
  367.         return 0;
  368.     else
  369.         return &pred->Next->Data;
  370. }
  371.  
  372. template <class T,class Alloc>
  373. void TMDoubleListImp<T,Alloc>::DoFlush( int del )
  374. {
  375.     TMDoubleListElement<T,Alloc> *current = Head.Next;
  376.     while( current != &Tail )
  377.         {
  378.         TMDoubleListElement<T,Alloc> *temp = current;
  379.         current = current->Next;
  380.         if( del != 0 )
  381.             RemoveData( temp );
  382.         delete temp;
  383.         }
  384.     InitList();
  385. }
  386.  
  387. template <class T,class Alloc>
  388. void TMDoubleListImp<T,Alloc>::ForEach( IterFunc f, void *args
  389.                                  )
  390. {
  391.     TMDoubleListElement<T,Alloc> *cur = Head.Next;
  392.     while( cur->Next != cur )
  393.         {
  394.         f( cur->Data, args );
  395.         cur = cur->Next;
  396.         }
  397. }
  398.  
  399. template <class T,class Alloc>
  400. T *TMDoubleListImp<T,Alloc>::FirstThat( CondFunc cond, void *args ) const
  401. {
  402.     TMDoubleListElement<T,Alloc> *cur = Head.Next;
  403.     while( cur->Next != cur )
  404.         if( cond( cur->Data, args ) != 0 )
  405.             return &(cur->Data);
  406.         else
  407.             cur = cur->Next;
  408.     return 0;
  409. }
  410.  
  411. template <class T,class Alloc>
  412. T *TMDoubleListImp<T,Alloc>::LastThat( CondFunc cond, void *args ) const
  413. {
  414.     T *res = 0;
  415.     TMDoubleListElement<T,Alloc> *cur = Head.Next;
  416.     while( cur->Next != cur )
  417.         {
  418.         if( cond( cur->Data, args ) != 0 )
  419.             res = &(cur->Data);
  420.         cur = cur->Next;
  421.         }
  422.     return res;
  423. }
  424.  
  425. #if defined( BI_OLDNAMES )
  426. #define BI_MDoubleListImp TMDoubleListImp
  427. #endif
  428.  
  429. /*------------------------------------------------------------------------*/
  430. /*                                                                        */
  431. /*  template <class T,class Alloc> class TMDoubleListIteratorImp          */
  432. /*                                                                        */
  433. /*  Implements a double list iterator.  This iterator works with any      */
  434. /*  direct double list.  For indirect lists, see                          */
  435. /*  TMIDoubleListIteratorImp.                                             */
  436. /*                                                                        */
  437. /*------------------------------------------------------------------------*/
  438.  
  439. template <class T,class Alloc> class TMSDoubleListImp;
  440.  
  441. template <class T,class Alloc> class TMDoubleListIteratorImp
  442. {
  443.  
  444. public:
  445.  
  446.     TMDoubleListIteratorImp( const TMDoubleListImp<T,Alloc>& l )
  447.         {
  448.         List = &l;
  449.         Cur = List->Head.Next;
  450.         }
  451.  
  452.     TMDoubleListIteratorImp( const TMSDoubleListImp<T,Alloc>& l );
  453.  
  454.     operator int()
  455.         {
  456.         return Cur != &(List->Head) && Cur != &(List->Tail);
  457.         }
  458.  
  459.     const T& Current()
  460.         {
  461.         PRECONDITION( int(*this) != 0 );
  462.         return Cur->Data;
  463.         }
  464.  
  465.     const T& operator ++ ( int )
  466.         {
  467.         PRECONDITION( Cur != &(List->Tail) );
  468.         TMDoubleListElement<T,Alloc> *temp = Cur;
  469.         Cur = Cur->Next;
  470.         return temp->Data;
  471.         }
  472.  
  473.     const T& operator ++ ()
  474.         {
  475.         PRECONDITION( Cur->Next != &(List->Tail) );
  476.         Cur = Cur->Next;
  477.         return Cur->Data;
  478.         }
  479.  
  480.     const T& operator -- ( int )
  481.         {
  482.         PRECONDITION( Cur != &(List->Head) );
  483.         TMDoubleListElement<T,Alloc> *temp = Cur;
  484.         Cur = Cur->Prev;
  485.         return temp->Data;
  486.         }
  487.  
  488.     const T& operator -- ()
  489.         {
  490.         PRECONDITION( Cur->Prev != &(List->Head) );
  491.         Cur = Cur->Prev;
  492.         return Cur->Data;
  493.         }
  494.  
  495.     void Restart()
  496.         {
  497.         Cur = List->Head.Next;
  498.         }
  499.  
  500.     void RestartAtTail()
  501.         {
  502.         Cur = List->Tail.Prev;
  503.         }
  504.  
  505. #if defined( BI_OLDNAMES )
  506.     T current() { return Current(); }
  507.     void restart() { Restart(); }
  508. #endif
  509.  
  510.  
  511. private:
  512.  
  513.     const TMDoubleListImp<T,Alloc> *List;
  514.     TMDoubleListElement<T,Alloc> *Cur;
  515.  
  516. };
  517.  
  518. #if defined( BI_OLDNAMES )
  519. #define BI_MDoubleListIteratorImp TMDoubleListIteratorImp
  520. #endif
  521.  
  522. /*------------------------------------------------------------------------*/
  523. /*                                                                        */
  524. /*  template <class T> class TDoubleListImp                               */
  525. /*  template <class T> class TDoubleListIteratorImp                       */
  526. /*                                                                        */
  527. /*  Implements a double-linked list of objects of type T using            */
  528. /*  TStandardAllocator as its memory manager. Assumes that T has          */
  529. /*  meaningful copy semantics and a default constructor.                  */
  530. /*                                                                        */
  531. /*------------------------------------------------------------------------*/
  532.  
  533. template <class T> class TSDoubleListImp;
  534.  
  535. template <class T> class TDoubleListImp :
  536.     public TMDoubleListImp<T,TStandardAllocator>
  537. {
  538. };
  539.  
  540. template <class T> class TDoubleListIteratorImp :
  541.     public TMDoubleListIteratorImp<T,TStandardAllocator>
  542. {
  543.  
  544. public:
  545.  
  546.     TDoubleListIteratorImp( const TDoubleListImp<T>& l ) :
  547.         TMDoubleListIteratorImp<T,TStandardAllocator>(l) {}
  548.  
  549.     TDoubleListIteratorImp( const TSDoubleListImp<T>& l ) :
  550.         TMDoubleListIteratorImp<T,TStandardAllocator>(l) {}
  551.  
  552. };
  553.  
  554. #if defined( BI_OLDNAMES )
  555. #define BI_DoubleListImp TDoubleListImp
  556. #define BI_DoubleListIteratorImp TDoubleListIteratorImp
  557. #endif
  558.  
  559. /*------------------------------------------------------------------------*/
  560. /*                                                                        */
  561. /*  template <class T,class Alloc> class TMSDoubleListImp                 */
  562. /*  template <class T,class Alloc> class TMSDoubleListIteratorImp         */
  563. /*                                                                        */
  564. /*  Implements a managed sorted double-linked list of objects of type T.  */
  565. /*  Assumes that T has meaningful copy semantics, a meaningful            */
  566. /*  < operator, and a default constructor.                                */
  567. /*                                                                        */
  568. /*------------------------------------------------------------------------*/
  569.  
  570. template <class T,class Alloc> class TMSDoubleListImp :
  571.     private TMDoubleListImp<T,Alloc>
  572. {
  573.     typedef TMDoubleListImp<T,Alloc> Parent;
  574.  
  575. public:
  576.  
  577.     friend TMDoubleListIteratorImp<T,Alloc>;
  578.  
  579.     int Add( const T& t );
  580.  
  581.     Parent::IterFunc;
  582.     Parent::CondFunc;
  583.     Parent::PeekHead;
  584.     Parent::PeekTail;
  585.     Parent::Detach;
  586.     Parent::Find;
  587.     Parent::Flush;
  588.     Parent::IsEmpty;
  589.     Parent::GetItemsInContainer;
  590.     Parent::ForEach;
  591.     Parent::FirstThat;
  592.     Parent::LastThat;
  593.     Parent::operator delete;
  594. #if !defined(BI_NO_ARRAYNEW)
  595.     Parent::operator delete [];
  596. #endif
  597.  
  598. #if defined( BI_OLDNAMES )
  599.     void add( const T& t ) { Add(t); }
  600.     Parent::peekHead;
  601.     Parent::peekTail;
  602.     Parent::detach;
  603.     Parent::flush;
  604.     Parent::isEmpty;
  605.     Parent::getItemsInContainer;
  606.     Parent::forEach;
  607.     Parent::firstThat;
  608.     Parent::lastThat;
  609. #endif  // BI_OLDNAMES
  610.  
  611. protected:
  612.  
  613.     Parent::Head;
  614.     Parent::Tail;
  615.     Parent::ItemsInContainer;
  616.     Parent::DoDetach;
  617.     Parent::DoDetachAtHead;
  618.     Parent::DoDetachAtTail;
  619.     Parent::DoFlush;
  620.  
  621.     virtual TMDoubleListElement<T,Alloc> *FindDetach( const T& );
  622.     virtual TMDoubleListElement<T,Alloc> *FindPred( const T& );
  623.  
  624. };
  625.  
  626. template <class T,class Alloc> class TMSDoubleListIteratorImp :
  627.     public TMDoubleListIteratorImp<T,Alloc>
  628. {
  629.  
  630. public:
  631.  
  632.     TMSDoubleListIteratorImp( const TMSDoubleListImp<T,Alloc>& l ) :
  633.         TMDoubleListIteratorImp<T,Alloc>(l) {}
  634.  
  635. };
  636.  
  637. template <class T,class Alloc>
  638. int TMSDoubleListImp<T,Alloc>::Add( const T& t )
  639. {
  640.     new TMDoubleListElement<T,Alloc>( t, FindPred(t) );
  641.     ItemsInContainer++;
  642.     return 1;
  643. }
  644.  
  645. template <class T,class Alloc>
  646. TMDoubleListElement<T,Alloc>*TMSDoubleListImp<T,Alloc>::FindDetach(const T&t)
  647. {
  648.     TMDoubleListElement<T,Alloc> *res = FindPred(t);
  649.     if( res != 0 &&
  650.         res->Next->Data == t )
  651.         return res;
  652.     else
  653.         return &Tail;
  654. }
  655.  
  656. template <class T,class Alloc>
  657. TMDoubleListElement<T,Alloc>*TMSDoubleListImp<T,Alloc>::FindPred(const T& t)
  658. {
  659.     Tail.Data = t;
  660.     TMDoubleListElement<T,Alloc> *cursor = &Head;
  661.     while( cursor->Next->Data < t )
  662.         cursor = cursor->Next;
  663.     Tail.Data = T();
  664.     return cursor;
  665. }
  666.  
  667. // constructor for TMDoubleListIteratorImp
  668. template <class T,class Alloc>
  669. TMDoubleListIteratorImp<T,Alloc>::TMDoubleListIteratorImp(
  670.     const TMSDoubleListImp<T,Alloc>& l )
  671. {
  672.     List = &l;
  673.     Cur = List->Head.Next;
  674. }
  675.  
  676. #if defined( BI_OLDNAMES )
  677. #define BI_MSDoubleListImp TMSDoubleListImp
  678. #define BI_MSDoubleListIteratorImp TMSDoubleListIteratorImp
  679. #endif
  680.  
  681. /*------------------------------------------------------------------------*/
  682. /*                                                                        */
  683. /*  template <class T> class TSDoubleListImp                              */
  684. /*  template <class T> class TSDoubleListIteratorImp                      */
  685. /*                                                                        */
  686. /*  Implements a sorted double-linked list of objects of type T, using    */
  687. /*  TStandardAllocator as its memory manager. Assumes that T has          */
  688. /*  meaningful copy semantics, a meaningful < operator, and a default     */
  689. /*  constructor.                                                          */
  690. /*                                                                        */
  691. /*------------------------------------------------------------------------*/
  692.  
  693. template <class T> class TSDoubleListImp :
  694.     public TMSDoubleListImp<T,TStandardAllocator>
  695. {
  696. };
  697.  
  698. template <class T> class TSDoubleListIteratorImp :
  699.     public TMSDoubleListIteratorImp<T,TStandardAllocator>
  700. {
  701.  
  702. public:
  703.  
  704.     TSDoubleListIteratorImp( const TSDoubleListImp<T>& l ) :
  705.         TMSDoubleListIteratorImp<T,TStandardAllocator>(l) {}
  706.  
  707. };
  708.  
  709. #if defined( BI_OLDNAMES )
  710. #define BI_SDoubleListImp TSDoubleListImp
  711. #define BI_SDoubleListIteratorImp TSDoubleListIteratorImp
  712. #endif
  713.  
  714. /*------------------------------------------------------------------------*/
  715. /*                                                                        */
  716. /*  template <class T,class List,class Alloc>                             */
  717. /*  class TMInternalIDoubleListImp                                        */
  718. /*                                                                        */
  719. /*  Implements a managed double-linked list of pointers to objects of     */
  720. /*  type T. This is implemented through the form of TMDoubleListImp       */
  721. /*  specified by List.  Since pointers always have meaningful copy        */
  722. /*  semantics, this class can handle any type of object.                  */
  723. /*                                                                        */
  724. /*------------------------------------------------------------------------*/
  725.  
  726. template <class T,class List,class Alloc> class TMInternalIDoubleListImp :
  727.     public List
  728. {
  729.  
  730.     typedef List Parent;
  731.  
  732. public:
  733.  
  734.     typedef void (*IterFunc)(T&, void *);
  735.     typedef int  (*CondFunc)(const T&, void *);
  736.  
  737.     T *PeekHead() const
  738.         {
  739.         return STATIC_CAST(T *, STATIC_CAST(void *, Parent::PeekHead()));
  740.         }
  741.  
  742.     T *PeekTail() const
  743.         {
  744.         return STATIC_CAST(T *, STATIC_CAST(void *, Parent::PeekTail()));
  745.         }
  746.  
  747.     int Add( T *t )
  748.         {
  749.         return Parent::Add( t );
  750.         }
  751.  
  752.     int Detach( T *t, int del = 0 )
  753.         {
  754.         return Parent::DoDetach( t, del );
  755.         }
  756.  
  757.     int DetachAtHead( int del = 0 )
  758.         {
  759.         return Parent::DoDetachAtHead( del );
  760.         }
  761.  
  762.     int DetachAtTail( int del = 0 )
  763.         {
  764.         return Parent::DoDetachAtTail( del );
  765.         }
  766.  
  767.     T *Find( const T *t );
  768.  
  769.     void Flush( int del = 0 )
  770.         {
  771.         DoFlush( del );
  772.         }
  773.  
  774.     void ForEach( IterFunc iter, void * );
  775.     T *FirstThat( CondFunc cond, void * ) const;
  776.     T *LastThat( CondFunc cond, void * ) const;
  777.  
  778. #if defined( BI_OLDNAMES )
  779.     T *peekHead() const { return PeekHead(); }
  780.     T *peekTail() const { return PeekTail(); }
  781.  
  782.     void add( T *t ) { Add(t); }
  783.     void detach( T *t, int del = 0 ) { Detach( t, del ); }
  784.     void forEach( IterFunc iter, void *args )
  785.         { ForEach( iter, args ); }
  786.     T *firstThat(  CondFunc cond, void *args ) const
  787.         { return FirstThat( cond, args ); }
  788.     T *lastThat( CondFunc cond, void *args ) const
  789.         { return LastThat( cond, args ); }
  790. #endif  // BI_OLDNAMES
  791.  
  792. protected:
  793.  
  794.     virtual TMDoubleListElement<TVoidPointer,Alloc> *FindPred( const TVoidPointer& ) = 0;
  795.  
  796. private:
  797.  
  798.     virtual void RemoveData( TMDoubleListElement<TVoidPointer,Alloc> *block )
  799.         {
  800.         delete STATIC_CAST(T *,STATIC_CAST(void *,block->Data));
  801.         }
  802.  
  803. };
  804.  
  805. template <class T, class List, class Alloc>
  806. T *TMInternalIDoubleListImp<T,List,Alloc>::Find( const T *t )
  807. {
  808.     TMDoubleListElement<TVoidPointer,Alloc> *pred = FindPred(t);
  809.     if( pred->Next == &Tail )
  810.         return 0;
  811.     else
  812.         return STATIC_CAST(T *,STATIC_CAST(void *,pred->Next->Data));
  813. }
  814.  
  815. template <class T, class List, class Alloc>
  816. void TMInternalIDoubleListImp<T,List,Alloc>::ForEach( IterFunc iter,
  817.                                                       void *args )
  818. {
  819.     TMDoubleListElement<TVoidPointer,Alloc> *cur = Head.Next;
  820.     while( cur->Next != cur )
  821.         {
  822.         iter( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args );
  823.         cur = cur->Next;
  824.         }
  825. }
  826.  
  827. template <class T, class List,class Alloc> T *
  828. TMInternalIDoubleListImp<T,List,Alloc>::FirstThat( CondFunc cond,
  829.                                                    void *args ) const
  830. {
  831.     TMDoubleListElement<TVoidPointer,Alloc> *cur = Head.Next;
  832.     while( cur->Next != cur )
  833.         if( cond( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args ) != 0 )
  834.             return STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
  835.         else
  836.             cur = cur->Next;
  837.     return 0;
  838. }
  839.  
  840. template <class T, class List, class Alloc> T *
  841. TMInternalIDoubleListImp<T,List,Alloc>::LastThat( CondFunc cond,
  842.                                                   void *args ) const
  843. {
  844.     T *res = 0;
  845.     TMDoubleListElement<TVoidPointer,Alloc> *cur = Head.Next;
  846.     while( cur->Next != cur )
  847.         {
  848.         if( cond( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args ) != 0 )
  849.             res = STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
  850.         cur = cur->Next;
  851.         }
  852.     return res;
  853. }
  854.  
  855. template <class T,class List,class Alloc>
  856. class TMInternalIDoubleListIteratorImp :
  857.     public TMDoubleListIteratorImp<TVoidPointer,Alloc>
  858. {
  859.  
  860.     typedef TMDoubleListIteratorImp<TVoidPointer,Alloc> Parent;
  861.  
  862. public:
  863.  
  864.     TMInternalIDoubleListIteratorImp( const TMInternalIDoubleListImp<T,List,Alloc>& l ) :
  865.         TMDoubleListIteratorImp<TVoidPointer,Alloc>(l) {}
  866.  
  867.     T *Current()
  868.         {
  869.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::Current()));
  870.         }
  871.  
  872.     T *operator ++ (int)
  873.         {
  874.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++(1)));
  875.         }
  876.  
  877.     T *operator ++ ()
  878.         {
  879.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++()));
  880.         }
  881.  
  882.     T *operator -- (int)
  883.         {
  884.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator--(1)));
  885.         }
  886.  
  887.     T *operator -- ()
  888.         {
  889.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator--()));
  890.         }
  891.  
  892. #if defined( BI_OLDNAMES )
  893.     T *current() { return Current(); }
  894. #endif  // BI_OLDNAMES
  895.  
  896. };
  897.  
  898. #if defined( BI_OLDNAMES )
  899. #define BI_MInternalIDoubleListImp TMInternalIDoubleListImp
  900. #endif
  901.  
  902. /*------------------------------------------------------------------------*/
  903. /*                                                                        */
  904. /*  template <class T,class Alloc> class TMIDoubleListImp                 */
  905. /*  template <class T,class Alloc> class TMIDoubleListIteratorImp         */
  906. /*                                                                        */
  907. /*  Implements a double-linked list of pointers to objects of             */
  908. /*  type T.  This is implemented through the template                     */
  909. /*  TMInternalIDoubleListImp. Since pointers always have meaningful       */
  910. /*  copy semantics, this class can handle any type of object.             */
  911. /*                                                                        */
  912. /*------------------------------------------------------------------------*/
  913.  
  914. template <class T,class Alloc> class TMIDoubleListIteratorImp;
  915.  
  916. template <class T,class Alloc> class TMIDoubleListImp :
  917.     private TMInternalIDoubleListImp<T,TMDoubleListImp<TVoidPointer,Alloc>,Alloc >
  918. {
  919.  
  920.     typedef TMInternalIDoubleListImp<T,TMDoubleListImp<TVoidPointer,Alloc>,Alloc > Parent;
  921.  
  922. public:
  923.  
  924.     friend TMIDoubleListIteratorImp<T,Alloc>;
  925.  
  926.     Parent::IterFunc;
  927.     Parent::CondFunc;
  928.     Parent::PeekHead;
  929.     Parent::PeekTail;
  930.     Parent::Add;
  931.     Parent::AddAtHead;
  932.     Parent::AddAtTail;
  933.     Parent::Detach;
  934.     Parent::DetachAtHead;
  935.     Parent::DetachAtTail;
  936.     Parent::Find;
  937.     Parent::Flush;
  938.     Parent::IsEmpty;
  939.     Parent::GetItemsInContainer;
  940.     Parent::ForEach;
  941.     Parent::FirstThat;
  942.     Parent::LastThat;
  943.     Parent::operator delete;
  944. #if !defined(BI_NO_ARRAYNEW)
  945.     Parent::operator delete [];
  946. #endif
  947.  
  948. #if defined( BI_OLDNAMES )
  949.     Parent::peekHead;
  950.     Parent::peekTail;
  951.     Parent::add;
  952.     Parent::addAtTail;
  953.     Parent::detach;
  954.     Parent::flush;
  955.     Parent::isEmpty;
  956.     Parent::forEach;
  957.     Parent::firstThat;
  958.     Parent::lastThat;
  959. #endif  // BI_OLDNAMES
  960.  
  961. protected:
  962.  
  963.     Parent::Head;
  964.     Parent::Tail;
  965.     Parent::ItemsInContainer;
  966.  
  967.     virtual TMDoubleListElement<TVoidPointer,Alloc> *FindPred(const TVoidPointer&);
  968.  
  969. };
  970.  
  971. template <class T,class Alloc> class TMIDoubleListIteratorImp :
  972.     public TMInternalIDoubleListIteratorImp<T,TMDoubleListImp<TVoidPointer,Alloc>,Alloc>
  973. {
  974.  
  975. public:
  976.  
  977.     TMIDoubleListIteratorImp( const TMIDoubleListImp<T,Alloc>& l ) :
  978.         TMInternalIDoubleListIteratorImp<T,TMDoubleListImp<TVoidPointer,Alloc>,Alloc>( l ) {}
  979.  
  980. };
  981.  
  982. template <class T,class Alloc>
  983. TMDoubleListElement<TVoidPointer,Alloc>
  984. *TMIDoubleListImp<T,Alloc>::FindPred( const TVoidPointer& t )
  985. {
  986.     Tail.Data = t;
  987.     TMDoubleListElement<TVoidPointer,Alloc> *cursor = &Head;
  988.     while( !(*STATIC_CAST(T *,STATIC_CAST(void *,t)) ==
  989.              *STATIC_CAST(T *,STATIC_CAST(void *,cursor->Next->Data))) )
  990.         cursor = cursor->Next;
  991.     Tail.Data = TVoidPointer();
  992.     return cursor;
  993. }
  994.  
  995. #if defined( BI_OLDNAMES )
  996. #define BI_MIDoubleListImp TMIDoubleListImp
  997. #define BI_MIDoubleListIteratorImp TMIDoubleListIteratorImp
  998. #endif
  999.  
  1000. /*------------------------------------------------------------------------*/
  1001. /*                                                                        */
  1002. /*  template <class T> class TIDoubleListImp                              */
  1003. /*  template <class T> class TIDoubleListIteratorImp                      */
  1004. /*                                                                        */
  1005. /*  Implements a double-linked list of pointers to objects of             */
  1006. /*  type T using TStandardAllocator as its memory manager.                */
  1007. /*  This is implemented through the template                              */
  1008. /*  TMInternalIDoubleListImp. Since pointers always have meaningful       */
  1009. /*  copy semantics, this class can handle any type of object.             */
  1010. /*                                                                        */
  1011. /*------------------------------------------------------------------------*/
  1012.  
  1013. template <class T> class TIDoubleListImp :
  1014.     public TMIDoubleListImp<T,TStandardAllocator>
  1015. {
  1016. };
  1017.  
  1018. template <class T> class TIDoubleListIteratorImp :
  1019.     public TMIDoubleListIteratorImp<T,TStandardAllocator>
  1020. {
  1021.  
  1022. public:
  1023.  
  1024.     TIDoubleListIteratorImp( const TIDoubleListImp<T>& l ) :
  1025.         TMIDoubleListIteratorImp<T,TStandardAllocator>( l ) {}
  1026.  
  1027. };
  1028.  
  1029. #if defined( BI_OLDNAMES )
  1030. #define BI_IDoubleListImp TIDoubleListImp
  1031. #define BI_IDoubleListIteratorImp TIDoubleListIteratorImp
  1032. #endif
  1033.  
  1034. /*------------------------------------------------------------------------*/
  1035. /*                                                                        */
  1036. /*  template <class T,class Alloc> class TMISDoubleListImp                */
  1037. /*  template <class T,class Alloc> class TMISDoubleListIteratorImp        */
  1038. /*                                                                        */
  1039. /*  Implements a managed sorted double-linked list of pointers to         */
  1040. /*  objects of type T.  This is implemented through the template          */
  1041. /*  TMInternalIDoubleListImp. Since pointers always have meaningful       */
  1042. /*  copy semantics, this class can handle any type of object.             */
  1043. /*                                                                        */
  1044. /*------------------------------------------------------------------------*/
  1045.  
  1046. template <class T,class Alloc> class TMISDoubleListIteratorImp;
  1047.  
  1048. template <class T,class Alloc> class TMISDoubleListImp :
  1049.     private TMInternalIDoubleListImp<T,TMSDoubleListImp<TVoidPointer,Alloc>,Alloc>
  1050. {
  1051.  
  1052.     typedef TMInternalIDoubleListImp<T, TMSDoubleListImp<TVoidPointer,Alloc>, Alloc > Parent;
  1053.  
  1054. public:
  1055.  
  1056.     friend TMISDoubleListIteratorImp<T,Alloc>;
  1057.  
  1058.     Parent::IterFunc;
  1059.     Parent::CondFunc;
  1060.     Parent::PeekHead;
  1061.     Parent::PeekTail;
  1062.     Parent::Add;
  1063.     Parent::Detach;
  1064.     Parent::DetachAtHead;
  1065.     Parent::DetachAtTail;
  1066.     Parent::Find;
  1067.     Parent::Flush;
  1068.     Parent::IsEmpty;
  1069.     Parent::GetItemsInContainer;
  1070.     Parent::ForEach;
  1071.     Parent::FirstThat;
  1072.     Parent::LastThat;
  1073.     Parent::operator delete;
  1074. #if !defined(BI_NO_ARRAYNEW)
  1075.     Parent::operator delete [];
  1076. #endif
  1077.  
  1078. protected:
  1079.  
  1080.     Parent::Head;
  1081.     Parent::Tail;
  1082.     Parent::ItemsInContainer;
  1083.  
  1084.     virtual TMDoubleListElement<TVoidPointer,Alloc> *FindDetach(const TVoidPointer&);
  1085.     virtual TMDoubleListElement<TVoidPointer,Alloc> *FindPred(const TVoidPointer&);
  1086.  
  1087. };
  1088.  
  1089. template <class T,class Alloc> class TMISDoubleListIteratorImp :
  1090.     public TMInternalIDoubleListIteratorImp<T,TMSDoubleListImp<TVoidPointer,Alloc>,Alloc>
  1091. {
  1092.  
  1093. public:
  1094.  
  1095.     TMISDoubleListIteratorImp( const TMISDoubleListImp<T,Alloc>& l ) :
  1096.         TMInternalIDoubleListIteratorImp<T,TMSDoubleListImp<TVoidPointer,Alloc>,Alloc>( l ) {}
  1097.  
  1098. };
  1099.  
  1100. template <class T,class Alloc>
  1101. TMDoubleListElement<TVoidPointer,Alloc>
  1102. *TMISDoubleListImp<T,Alloc>::FindDetach( const TVoidPointer& t )
  1103. {
  1104.     TMDoubleListElement<TVoidPointer,Alloc> *res = FindPred(t);
  1105.     if( res == 0 || res->Next == &Tail )
  1106.         return &Tail;
  1107.     else if(
  1108.         *STATIC_CAST(T *,STATIC_CAST(void *,res->Next->Data)) ==
  1109.         *STATIC_CAST(T *,STATIC_CAST(void *,t)) )
  1110.             return res;
  1111.     else
  1112.         return &Tail;
  1113. }
  1114.  
  1115. template <class T,class Alloc>
  1116. TMDoubleListElement<TVoidPointer,Alloc>
  1117. *TMISDoubleListImp<T,Alloc>::FindPred( const TVoidPointer& t )
  1118. {
  1119.     Tail.Data = t;
  1120.     TMDoubleListElement<TVoidPointer,Alloc> *cursor = &Head;
  1121.     while( *STATIC_CAST(T *,STATIC_CAST(void *,cursor->Next->Data)) <
  1122.            *STATIC_CAST(T *,STATIC_CAST(void *,t)) )
  1123.         cursor = cursor->Next;
  1124.     Tail.Data = TVoidPointer();
  1125.     return cursor;
  1126. }
  1127.  
  1128. #if defined( BI_OLDNAMES )
  1129. #define BI_MISDoubleListImp TMISDoubleListImp
  1130. #define BI_MISDoubleListIteratorImp TMISDoubleListIteratorImp
  1131. #endif
  1132.  
  1133. /*------------------------------------------------------------------------*/
  1134. /*                                                                        */
  1135. /*  template <class T> class TISDoubleListImp                             */
  1136. /*  template <class T> class TISDoubleListIteratorImp                     */
  1137. /*                                                                        */
  1138. /*  Implements a managed sorted double-linked list of pointers to         */
  1139. /*  objects of type T using TStandardAllocator as its memory manager.     */
  1140. /*  This is implemented through the template                              */
  1141. /*  TMInternalIDoubleListImp. Since pointers always have meaningful       */
  1142. /*  copy semantics, this class can handle any type of object.             */
  1143. /*                                                                        */
  1144. /*------------------------------------------------------------------------*/
  1145.  
  1146. template <class T> class TISDoubleListImp :
  1147.     public TMISDoubleListImp<T,TStandardAllocator>
  1148. {
  1149. };
  1150.  
  1151. template <class T> class TISDoubleListIteratorImp :
  1152.     public TMISDoubleListIteratorImp<T,TStandardAllocator>
  1153. {
  1154.  
  1155. public:
  1156.  
  1157.     TISDoubleListIteratorImp( const TISDoubleListImp<T>& l ) :
  1158.         TMISDoubleListIteratorImp<T,TStandardAllocator>( l ) {}
  1159.  
  1160. };
  1161.  
  1162. #if defined(BI_NAMESPACE)
  1163. }   // namespace ClassLib
  1164. #endif
  1165.  
  1166. #if defined( BI_OLDNAMES )
  1167. #define BI_ISDoubleListImp TISDoubleListImp
  1168. #define BI_ISDoubleListIteratorImp TISDoubleListIteratorImp
  1169. #endif
  1170.  
  1171. #if defined( BI_CLASSLIB_NO_po )
  1172. #pragma option -po.
  1173. #endif
  1174.  
  1175. #pragma option -Vo.
  1176.  
  1177. #endif  // CLASSLIB_DLISTIMP_H
  1178.  
  1179.